package com.fr.lintcode;

import org.junit.Test;

public class Q129 {

	/**
	 * @param hashTable: A list of The first node of linked list
	 * @return: A list of The first node of linked list which have twice size
	 */
	public ListNode[] rehashing(ListNode[] hashTable) {
		// write your code here
		if (hashTable == null) {
			return null;
		}
		int capacity = hashTable.length;
		capacity = capacity * 2;
		ListNode[] newHashTable = new ListNode[capacity];
		for (ListNode ln : hashTable) {
			ListNode tmp = ln;
			while (tmp != null) {
				ListNode next = tmp.next;
				int hash ;
				if(tmp.val >= 0) {
					hash = tmp.val % capacity;
				}else {
					hash = (tmp.val % capacity) + capacity;
				}
				tmp.next = null;
				ListNode head = newHashTable[hash];
				if(head == null) {
					newHashTable[hash] = tmp;
				}else {
					ListNode parent = null;
					while(head != null) {
						parent = head;
						head = head.next;
					}
					parent.next = tmp;
				}
				
				tmp = next;
			}
		}
		return newHashTable;
	}
	
	
	@Test
	public void testA(){
//		null,null,42->32->null,-7->null,null
		ListNode[] newHashTable = new ListNode[5];
		ListNode n1 = new ListNode(42);
		ListNode n2 = new ListNode(32);
		n1.next = n2;
		ListNode n3 = new ListNode(-7);
		newHashTable[2] = n1;
		newHashTable[3] = n3;
		ListNode[] rs = rehashing(newHashTable);
		for(ListNode l : rs) {
			System.out.println(l);
		}
		
	}
}
